package com.aikon.wht.paoshan.alg;

import java.util.HashMap;
import java.util.Map;

/**
 * 递归有利有弊，利是递归代码的表达力很强，写起来非常简洁；而弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题
 * 例如在影院中想知道自己在第几排可以问前一排，前一排也问他的前一排，直到第一排，在把结果依次告诉后面一排，这就是递和归的过程。
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfRecursion {

    // 1.递归公式 2.终止条件


    // 假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，
    // 请问走这 n 个台阶有多少种走法？如果有 7 个台阶，
    // 你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，
    // 总之走法有很多，那如何用编程求得总共有多少种走法呢？
    public static class Climb {

        /**
         * 避免重复计算，减少递归次数，减少栈溢出风险
         */
        private static final Map<Integer, Integer> CACHE = new HashMap<>();

        public static int calc(int n) {
            Integer val = CACHE.get(n);
            if (val != null) {
                return val;
            }
            if (n == 1) {
                return 1;
            }
            if (n == 2) {
                return 2;
            }
            val = calc(n - 1) + calc(n - 2);
            CACHE.put(n, val);
            return val;
        }

        public static void main(String[] args) {
            System.out.println(
                    calc(5)
            );

        }
    }
}

